Giám mục Cao Ðình Thuyên sinh ngày 07 tháng 12 năm 1926 tại giáo họ Tràng Lưu, giáo xứ Tràng Lưu, nay thuộc xã Lộc Yên, huyện Hương Khê, tỉnh Hà Tĩnh.[2] Nhiều tài liệu ghi ngày sinh của ông là 7 tháng 1 năm 1927.[3] Thân sinh ông Gioan Baotixita Cao Ðình Tùng và bà Anna Nguyễn Thị Ðích.[4]

Năm 11 tuổi ông được linh mục Phaolô Kim quản xứ Thượng Nậm đã nhận đỡ đầu và gửi đi Trường Tập Xuân Phong, đến ngày 13 tháng 8 năm 1938 thì nhập học tại đây.[4] Sau đúng bốn năm tại trường tập, cậu bé Thuyên được cho học tiếp tại tiểu chủng viện Xã Ðoài. Sau khi hoàn thành chương trình tiểu chủng viện, năm 1950, chủng sinh Phaolô Cao Đình Thuyên quyết định về giúp Sở Quản lý Nhà chung Xã Ðoài. Đầu năm 1955, chủng sinh Thuyên được mời gọi tiếp tục con đường tu học tại Ðại chủng viện Xã Ðoài.[4]

Con đường thăng tiến của chùng sinh Thuyên diễn ra khá nhanh: ngày 1 tháng 5 năm 1957, được gia nhập hàng giáo sĩ. Hai tháng sau đó, ngày 21 tháng 12, ông chịu các chức nhỏ. Hơn một năm sau, ngày 31 tháng 1 năm 1959, chủng sinh Thuyên trở thành Phụ phó tế rồi nhanh chóng trở thành Phó tế vào ngày 1 tháng 2 năm 1960.[4]